package leetcode;

/**
 * @author ：徐梦轲
 * @date ：2022/5/22 0022 10:00
 */


class ListNode {
     int val;
     ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

public class Solution {
    //方法1：先删除头节点外的其他符合条件的结点，头节点最后考虑
    //时间复杂度是O(n) 空间复杂度O(1)
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    //方法2：添加虚拟结点，遍历一遍，删除所有符合条件的结点
    //时间复杂度是O(n) 空间复杂度O(1)
    public ListNode removeElements2(ListNode head, int val) {
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode cur = head;
        ListNode pre = node;
        while(cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return node.next;
    }

    //方法3：递归
    //时间复杂度是O(n) 空间复杂度O(n)
    public ListNode removeElements3(ListNode head, int val) {
        if(head==null)
            return null;
        head.next=removeElements(head.next,val);
        if(head.val==val){
            return head.next;
        }else{
            return head;
        }
    }
}
